package algorithm.backtrack;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.Stack;
import java.util.function.Consumer;

public class BackTrackTest {

    public static void main(String[] args) {

    }

    @Test
    public void test() {
        System.out.println("test ");
        int[] arr = {1, 2, 3, 4, 5};
        ArrayList<List<Integer>> res = new ArrayList<>();
        backtrack1(arr, new int[arr.length], new Stack<>(), res);
        printRes(res);
    }

    private static void printRes(ArrayList<List<Integer>> res) {
        for (List<Integer> re : res) {
            for (Integer i : re) {
                System.out.print(i + ",");
            }
            System.out.println();
        }
        System.out.println(res.size());
    }

    /**
     * 全排列
     * 四个参数,前个是必须的,第三个是遍历的路径,第四个是存放路径的结果
     */
    public void backtrack1(int[] arr, int[] flag, Stack<Integer> path, List<List<Integer>> res) {

        //收集结果
        if (path.size() == arr.length) {
            List<Integer> ress = new ArrayList<>();
            for (Integer i : path) {
                ress.add(i);
            }
            res.add(ress);
        }

        for (int i = 0; i < arr.length; i++) {
            if (flag[i] == 1) continue;
            int e = arr[i];
            path.push(e);
            flag[i] = 1;
            backtrack1(arr, flag, path, res);
            flag[i] = 0;
            path.pop();
        }

    }

    @Test
    public void test2() {
        int[] arr = {1, 2, 3,};
        ArrayList<List<Integer>> res = new ArrayList<>();
        backtrack2(arr, 0, new Stack<>(), res);
        printRes(res);
    }

    /**
     * 组合
     * 分为两种, 所有情况的组合,和指定深度的组合
     * 组合不考虑顺序,只关注有或者没有, 所以 定义 startIndex 这个字段, 在往深入遍历时,只遍历 startIndex 之后的元素,就可以实现这种组合。
     */
    public void backtrack2(int[] arr, int startIndex, Stack<Integer> path, List<List<Integer>> res) {

        //所有情况的组合,把所有的路径打印出来
        if (path.size() > 0) {
            List<Integer> ress = new ArrayList<>();
            for (Integer i : path) {
                ress.add(i);
            }
            res.add(ress);
        }

        // 从 startIndex 开始
        for (int i = startIndex; i < arr.length; i++) {
            int e = arr[i];
            path.push(e);
            backtrack2(arr, i + 1, path, res);
            path.pop();
        }
    }

    @Test
    public void test3() {
        int[] arr = {1, 2, 3, 4};
        ArrayList<List<Integer>> res = new ArrayList<>();
        backtrack3(arr, 0, 2, new Stack<>(), res);
        printRes(res);
    }

    /**
     * 组合
     * 指定个数的组合
     */
    public void backtrack3(int[] arr, int startIndex, int k, Stack<Integer> path, List<List<Integer>> res) {

        //所有情况的组合,把所有的路径打印出来
        if (path.size() == k) {
            List<Integer> ress = new ArrayList<>();
            for (Integer i : path) {
                ress.add(i);
            }
            res.add(ress);
        }

        // 从 startIndex 开始
        for (int i = startIndex; i < arr.length; i++) {
            //减枝 如果path 跟 剩余数组 长度之和 小于 k  就终止循环
            if (path.size() + (arr.length - i) < k) {
                return;
            }

            int e = arr[i];
            path.push(e);
            // 打印查看路径
            path.forEach(integer -> System.out.println(integer));
            System.out.print(" -> " + e);
            System.out.println();
            backtrack3(arr, i + 1, k, path, res);
            path.pop();
        }
    }

    public void printCollection(Collection c) {

    }


}
